|
Borůvka's algorithm is an algorithm for finding a minimum spanning tree in a graph for which all edge weights are distinct. It was first published in 1926 by Otakar Borůvka as a method of constructing an efficient electricity network for Moravia. The algorithm was rediscovered by Choquet in 1938; again by Florek, Łukasiewicz, Perkal, Steinhaus, and Zubrzycki in 1951; and again by Sollin in 1965. Because Sollin was the only computer scientist in this list living in an English speaking country, this algorithm is frequently called Sollin's algorithm, especially in the parallel computing literature. The algorithm begins by first examining each vertex and adding the cheapest edge from that vertex to another in the graph, without regard to already added edges, and continues joining these groupings in a like manner until a tree spanning all vertices is completed. == Pseudocode == Designating each vertex or set of connected vertices a "component", pseudocode for Borůvka's algorithm is: Input: A connected graph G whose edges have distinct weights Initialize a forest T to be a set of one-vertex trees, one for each vertex of the graph. While T has more than one component: For each component C of T: Begin with an empty set of edges S For each vertex v in C: Find the cheapest edge from v to a vertex outside of C, and add it to S Add the cheapest edge in S to T Output: T is the minimum spanning tree of G. As in Kruskal's algorithm, tracking components of T can be done efficiently using a disjoint-set data structure. In graphs where edges have identical weights, edges with equal weights can be ordered based on the lexicographic order of their endpoints. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Borůvka's algorithm」の詳細全文を読む スポンサード リンク
|